1. Field of the Invention
The present invention relates to detection of epidemic outbreaks in a large population of hosts. In particular, the present invention relates to detection of an epidemic outbreak by making use of a particular type of Dynamic Bayesian Network which is defined herein as a Persistent Causal-Chain Dynamic Bayesian Network (PCCDBN).
2. Description of the Prior Art
A Bayesian Network is a type of Directed Acyclic Graph which is used to show causal relationships between random variables. A Directed Graph contains a set of nodes and a set of arrows describing a path from node to node. A node X is said to be a parent of another node Y if there is an arrow from X to Y. A Directed Acyclic Graph is a special type of Directed Graph in which there is no directed path from a node back to itself.
In a Bayesian Network, the nodes represent random variables and the arrows represent the fact that the child node may be conditionally dependent on the parent. The random variables may take on a discrete value such as true or false or a continuous value such as one of the real numbers.
In a Bayesian Network, for any node X the conditional probability that the random variable X takes on any particular value, given the value of all of X's parents is specified. Given these conditional probabilities, it is then possible to calculate the probability that an event occurred given other events occurring. This process is known as inference.
In a Bayesian Network, nodes are either hidden or observed. A hidden node, as opposed to an observed node, is a node whose value is not known. A node may be explicitly represented in the model but still hidden due to a lack of observable information. A random variable may also be hidden due to a lack of known conditional independencies, and thus not be represented by a node in the Bayesian network.
A Dynamic Bayesian Network (DBN) extends the concept of the Bayesian Network into the time dimension. In a Dynamic Bayesian Network, the Bayesian Network is repeated throughout time. Just as arrows create causal connections between nodes in a Bayesian Network, allows are used in a Dynamic Bayesian Network to causally link the network at one time instance to the network at the next time instance.
When a Dynamic Bayesian Network uses discrete random variables, it may be computationally intractable to solve for the conditional probabilities among nodes. Standard approaches using exact inference models require exponential time due to the large number of cross-temporal dependencies that exist between nodes. Such an exponential approach is intractable and cannot be solved in real time. Other inference models have been developed to solve the network in less than exponential time, however these approaches introduce approximations and cannot give exact solutions.
Thus, it would be beneficial to have an exact inference model that could solve a type of discrete Dynamic Bayesian Network in less than exponential time by taking advantage of certain properties of the network.